package lc20240602;

import lc20240521.TreeNode;

/**
 * @author 不知名帅哥
 * @version 1.0
 * @description 230. 二叉搜索树中第K小的元素
 * @date 2024/6/2 12:49
 */
public class GetKMinimum {
    int i = 0;
    int min;

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.right = new TreeNode(6);
        root.left = new TreeNode(3, new TreeNode(2, new TreeNode(1), null), new TreeNode(4));
        GetKMinimum getKMinimum = new GetKMinimum();
        System.out.println(getKMinimum.kthSmallest(root, 3));
    }

    public int kthSmallest(TreeNode root, int k) {
        inOrder(root, k);
        return min;
    }

    public void inOrder(TreeNode root, int k) {
        if (root == null) {
            return;
        }
        inOrder(root.left, k);
        //关键步骤，全局变量i==k的时候返回。
        if (i == k) {
            return;
        }
        i++;
        if (i == k) {
            min = root.val;
        }
        //之前是i=1，如下。不能在这个里面写return，会更新为新的root值。
//        if (i == k) {
//            min = root.val;
//        }
//        i++;
        inOrder(root.right, k);
    }
}
